/*
 * @lc app=leetcode.cn id=743 lang=swift
 *
 * [743] 网络延迟时间
 */

// @lc code=start
class Solution {
    func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
        var graph: [[(Int, Int)]] = Array(repeating: [], count: n+1)
        // 构造图
        for time in times {
            graph[time[0]].append((time[1], time[2]))
        }

        let distTo = dijkstra(k, graph)

        var res = 0
        for i in 1..<distTo.count {
            if distTo[i] == Int.max {
                // 有点不可达
                return -1
            }
            res = max(res, distTo[i])
        }

        return res
    }

    func dijkstra(_ start: Int, _ graph: [[(Int, Int)]]) -> [Int] {
        // 各个点的最短距离
        var distTo: [Int] = Array(repeating: Int.max, count: graph.count)
        distTo[start] = 0
        var pq: [(Int, Int)] = []
        pq.append((start, 0))

        while !pq.isEmpty {
            let curNode = pq.removeFirst()
            let curNodeId = curNode.0
            let curDistTo = curNode.1

            if curDistTo > distTo[curNodeId] {
                continue
            }

            for nextNode in graph[curNodeId] {
                let nextNodeId = nextNode.0
                let nextDistTo = nextNode.1 + curDistTo
                if nextDistTo < distTo[nextNodeId] {
                    // 更新最小距离
                    distTo[nextNodeId] = nextDistTo
                    pq.append((nextNodeId, nextDistTo))
                    pq.sort(by: { a, b in a.1 < b.1})
                }
            }
        }
        return distTo
    }
}
// @lc code=end

